package com.kaigejava.suanfa.lru;

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Scanner;

/**
 * @author 凯哥Java
 * @description 基于linkdeHashMap实现的lru算法
 * lru：最近最少使用的
 * 思路：
 * 1：实现get/put时候方法都是O(1)的时间复杂度
 * 2：每次get的时候需要将访问的节点提到队首
 * 3：每次put的时候，需要判断队列是否已经满了。满了则需要将节点删除。并将该节点放到队首，不满则直接放到队首
 *
 * 当put的时候，判断，如果
 * @company
 * @since 2022/11/9 11:39
 */
public class LRULinkedHashMap {

    /**
     *  缓存最大存放数量
     */
    private int cap;
    /**
     * 存放数据的链表
     */
    private LinkedHashMap<Integer,Integer> cache = new LinkedHashMap<>();

    /**
     * 有参构造
     * @param cap
     */
    public LRULinkedHashMap (int cap){
        this.cap = cap;
    }


    /**
     * 将某个key修改成最近使用的
     * @param key
     */
    private void makeRecently(int key){
        //先获取到值
        Integer val = cache.get(key);
        //删除当前key
        cache.remove(key);
        //重新将当前key放入到队列中
        cache.put(key,val);
    }


    /**
     * 插入数据
     * @param key
     * @param val
     */
    public void put(int key,int val){
        if(cache.containsKey(key)){
            //当前链表中已经存在了当前key.替换value
            cache.put(key,val);
            //将当前key设置到链表头
            makeRecently(key);
            return;
        }

        if(cap <= cache.size()){
            //当前满了。需要删除链表最后一个。
            Integer deleteKey = cache.keySet().iterator().next();
            //删除当前节点
            cache.remove(deleteKey);
        }
        //将新的key插入
        cache.put(key,val);
    }


    /**
     * 根据key获取 value
     * @param key
     * @return -1：没有
     */
    public int get(int key){
        if(!cache.containsKey(key)){
            return -1;
        }
        //先将当前key提到队首
        makeRecently(key);
        return cache.get(key);
    }

    public void print(){
        Iterator<Integer> iterator = cache.keySet().iterator();
        while(iterator.hasNext()){
            int key = iterator.next();
            System.out.print(key+"->"+ cache.get(key)+" ");
        }
        System.out.println();
    }


    public static void main(String[] args) {
        LRULinkedHashMap lruCache = new LRULinkedHashMap(5);
        Scanner sc = new Scanner(System.in);
        int key,val;
        while(true){
            System.out.println("请输入插入的key和val(以空格隔开,输入-1则结束)");
            key = sc.nextInt();
            if (key == -1) break;
            val = sc.nextInt();
            lruCache.put(key,val);
            lruCache.print();
        }
        while(true){
            System.out.println("请输入需要获取的key(输入-1则结束)");
            key = sc.nextInt();
            if (key == -1) break;
            System.out.println("key->val: "+key+"->"+lruCache.get(key));
            lruCache.print();
        }
    }
}
